1. Technical Field
The invention disclosed broadly relates to data processing systems and methods and more particularly relates to cryptographic systems and methods for use in data processing systems to enhance security.
2. Background Art
The following patents and patent applications are related to this invention and are incorporated herein by reference:
W. F. Ehrsam, et al., "Block Cipher System for Data Security," U.S. Pat. No. 3,958,081, issued May 18, 1976, assigned to IBM Corporation and incorporated herein by reference.
W. F. Ehrsam, et al., "Product Block Cipher System," U.S. Pat. No. 3,962,539, issued Jun. 8, 1976, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Secure Management of Keys Using Control Vectors," U.S. Pat. No. 4,941,176, issued Jul. 10, 1990, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Data Cryptography Operations Using Control Vectors," U.S. Pat. No. 4,918,728, issued Apr. 17, 1990, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Personal Identification Number Processing Using Control Vectors," U.S. Pat. No. 4,924,514, issued May 8, 1990, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Secure Management of Keys Using Extended Control Vectors," U.S. Pat. No. 4,924,515, issued May 8, 1990, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Secure Management of Keys Using Control Vectors with Multi-Path Checking," Ser. No. 07/596,637, filed Oct. 12, 1990, assigned to IBM Corporation and incorporated here by reference.
S. M. Matyas, et al., "Secure Cryptographic Operations Using Alternate Modes of Control Vector Enforcement," Ser. No. 07/574,012, filed Aug. 22, 1990, assigned to IBM Corporation and incorporated here by reference.
S. M. Matyas, et al., "Secure Key Management Using Programmable Control Control Vector Checking," U.S. Pat. No. 5,007,089, issued Apr. 9, 1991, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Secure Key Management Using Control Vector Translation," U.S. Pat. No. 54,993,069 issued Feb. 12, 1991, assigned to IBM Corporation and incorporated herein by reference.
B. Brachtl, et al., "Data Authentication Using Modification Detection Codes Based on a Public One Way Encryption Function," U.S. Pat. No. 4,908,861, issued Mar. 13, 1990, assigned to IBM Corporation and incorporated herein by reference.
D. Abraham, et al., "DEA-Based Pseudorandom Number Generator," IBM Technical Disclosure Bulletin, Vol. 35, No. 1B, pp. 431-434 (June 1992).
With the advent of electronic data processing, vast amounts of digital data are stored in large computer data bases and transmitted between computers and workstations linked together in complex communications networks. Cryptographic algorithms have been developed and implemented in products to encrypt and protect stored and transmitted data.
U.S. Pat. Nos. 3,958,081 and 3,962,539 describe an IBM-invented cryptographic algorithm that was adopted as a federal Data Encryption Standard (DES) on Jul. 15, 1977, and described in Federal Information Processing Standard FIPS 46-1. The DES algorithm was also adopted by the American National Standards Institute (ANSI) as the standard industry algorithm ("Data Encryption Algorithm (DEA)" X3.92), see ANSI X3.92-1981. The DEA is a symmetric (secret key) block cipher that encrypts a 64-bit input plaintext to produce a 64-bit output ciphertext using a secret 64-bit key. The 64-bit key consists of 56 independent key bits and 8 non-key bits that may be used for parity checking. The DEA is the most widely used commercial encryption algorithm. It has become a de facto international standard. The DEA is particularly suited for bulk data encryption. Hardware implementations of the DEA are able to encrypt several hundred megabits of data per second.
Other cryptographic algorithms have also been developed for commercial use, particularly public key algorithms. Public key encryption algorithms are described in a paper by W. Diffie and M. E. Hellman entitled "Privacy and Authentication: An Introduction to Cryptography," Proceedings of the IEEE, Vol. 67, No. 3, March 1979, pp. 397-427. In a public key cryptographic system, two keys are used, one for enciphering and one for deciphering. Public key algorithm systems are designed so that (1) it is easy to generate a random pair of inverse keys PU (for enciphering) and PR (for deciphering) and (2) it is easy to operate with PU and PR, but (3) it is computationally infeasible to compute PR from PU. Each user generates a pair of inverse transforms, PU and PR. He keeps the deciphering transformation PR secret, and makes the enciphering transformation PU public by placing it in a public directory. Anyone can now encrypt messages and send them to the user, but no one else can decipher messages intended for him. It is possible, and often desirable, to encipher with PU and decipher with PR. For this reason, PU is usually referred to as a public key and PR is usually referred to as a private key. A corollary feature of public key cryptographic systems is the provision of a digital signature which uniquely identifies the sender of a message. If user A wishes to send a signed message M to user B, he operates on it with his private key PR to produce the signed message S. PR was used as A's deciphering key when privacy was desired, but it is now used as his "enciphering" key. When user B receives the message S, he can recover the message M by operating on the ciphertext S with A's public PU. By successfully decrypting A's message, the receiver B has conclusive proof it came from the sender A. Examples of public key cryptography are provided in the following U.S. Pat. No. 4,218,582 to Hellman, et al., "Public Key Cryptographic Apparatus and Method;" U.S. Pat. No. 4,200,770 to Hellman, et al., "Cryptographic Apparatus and Method;" and U.S. Pat. No. 4,405,829 to Rivest, et al., "Cryptographic Communications System and Method."
The Data Encryption Algorithm (DEA), when used for data confidentiality purposes, is not able to be exported from the USA because of export regulations on cryptography. It cannot be freely imported in some other countries. Export regulation relief is generally given for electronic data processing applications involving data integrity, identification and authentication, one-way encryption of passwords, key management, and key distribution.
To overcome the restrictions imposed on cryptographic applications by U.S. government export regulations, the U.S. government has permitted the RSA algorithm to be exported and used for applications involving data integrity and key distribution provided that the length of the keys is restricted or limited to an agreed upon value. For example, where the RSA algorithm is used in a hybrid key distribution scheme to encrypt DEA keys for distribution from a sending device to a receiving device, the RSA keys are limited to 512 bits. Market demands continue to be received for a suitable, fast encryption algorithm for data confidentiality purposes, which can be freely exported from the United States. A small number of proprietary algorithms have been developed to satisfy this market demand, but the algorithm details (of course) have not been published.
A general problem with proprietary algorithms is that, by not disclosing the details of an algorithm, cryptographers, cryptanalysts, mathematicians, and the like cannot study the algorithm and validate its strength. Hence, users cannot be certain of the degree of protection afforded by such a cryptographic algorithm. The process of developing and validating a cryptographic algorithm, if properly done, is a lengthy and costly process. For example, it took IBM 17 man-years to develop and validate the DEA. Instead of developing a new cryptographic algorithm of suitable weakened strength, it would be particularly advantageous to produce a weakened version of the DEA--i.e., a DEA junior--by weakening only the key or restricting the key space to a smaller number of allowed key combinations and by not changing or altering the DEA algorithm itself (s-box functions, permutation, key schedule). In this way, the basic underlying strength of DEA is preserved, and therefore no inadvertent shortcut attack is introduced into DEA junior. But by weakening the key, DEA junior can be given a predictable cryptographic strength, or work factor, based on recovering an unknown key using a method of direct search or key exhaustion (i.e., trying one key after another). In this case, validating the key-weakening process is a relatively simple process compared to validating a new algorithm, with an apparent savings in cost and time to the developer. The strength of such a DEA-junior algorithm can be easily demonstrated to users. The ability for users and implementers to easily assess the security provided by such an algorithm is deemed essential for its acceptance. Thus, when data is encrypted with DEA-junior, users receive and are assured of a known, predictable level of cryptographic protection. In this case, relief from U.S. government export regulations is achieved by weakening the key, or by adjusting the number of allowable key combinations, to a level prescribed by the U.S. government. The prior art does not teach how keys belonging to a strong block cipher algorithm, such as the DEA, can be weakened for the purpose of constructing a weakened block cipher algorithm of known, predictable strength.
One possibility for weakening a DEA key is to fix certain key bits so there are fewer independent key bits within the key. U.S. Pat. No. 4,908,861 to Brachtl et al. discloses a method of fixing bits in a cryptographic key for the purpose of ensuring that two keys used by the one-way algorithm are different. The bits in a first key are set to B'10' and the bits in a second key are set to B'01'. By ensuring that the first and seconds keys are different, the algorithm construction prevents a rare, but possible case from occurring which would weaken the one-way algorithm. In this regard, Brachtl et al. teach how bit fixing can be used beneficially to improve cryptographic strength. Brachtl et al. do not teach how bit fixing can be used for the purpose of weakening cryptographic strength. The prior art does not teach how to beneficially weaken a key by fixing key bits.
For purposes of discussion, a weakened Data Encryption Algorithm (referred to above as DEA junior) shall be referred to hereafter as Commercial Data Masking (CDM).
U.S. Pat. Nos. 4,941,176, 4,918,728, 4,924,514, 4,924,515, 4,993,069, 5,007,089, and patent application Ser. Nos. 07/596,637, and 07/574,012, cited above, describe a cryptographic architecture incorporated a set of hardware-level cryptographic instructions for processing data, Personal Identification Numbers (PINs), and keys. A corresponding set of cryptographic services accessible at a cryptographic Application Programming Interface (API), and which can itself be implemented using the aforesaid hardware-level cryptographic instructions, is called The IBM Common Cryptographic Architecture, see Common Cryptographic Architecture Cryptographic Application Programming Interface, SC40-1675, IBM Corporation (1990).
The Common Cryptographic Architecture (CCA) is based on the Data Encryption Algorithm (DEA). The Cryptographic API describes a set of cryptographic services that provide data privacy, data integrity, cryptographic key installation and generation, electronic cryptographic key distribution, and Personal Identification Number (PIN) processing. The data privacy cryptographic services include Encipher and Decipher services for enciphering and deciphering data using the DEA. In situations where a CCA-compliant cryptographic device is exported from the United States to a destination that cannot receive the DEA-based Encipher and Decipher services, it would be desirable for the DEA-based Encipher and Decipher services to be replaced within the cryptographic device with CDM-based Encipher and Decipher services, i.e., data enciphering and deciphering services based on a Commercial Data Masking algorithm. Likewise, it would be advantageous for the keys used by the CDM-based Encipher and Decipher services to be of the same form and length as the keys used by the DEA-based Encipher and Decipher services, so that the keys used by both DEA-based and CDM-based services can be generated and distributed using the key management and key distribution services of CCA (i.e., without modification). In this way, two communicating devices may use the commercial data masking algorithm to mask data transmitted between them. That is, data is masked at a sending device by invoking a CDM Encipher service and masked data is unmasked at a receiving device by invoking a CDM Decipher service. But a potential problem arises when the keys for the DEA-based Encipher and Decipher services and the keys for the CDM-based Encipher and Decipher services are of the same form and length, and are generated and distributed using the same set of CCA key management and key distribution services. Unless the keys are tagged so that the keys for the DEA-based services cannot be mixed and used with the CDM-based services, it may be possible for an insider adversary to attack a DEA key using the following method: (a) feed a strong DEA key to a CDM-based Encipher service to encrypt a known plaintext, (b) use the known plaintext and produced ciphertext to recover the weakened CDM key via a key exhaustion attack. The recovered CDM key may reveal some of the key bits in the original DEA key, which would weaken the DEA key and reduce the work necessary to recover the remaining unknown key bits. The prior art does not teach how two different algorithms of different strengths such as the DEA and CDM can be implemented safely in the same cryptographic system. That is, the prior art does not teach how the keys of both algorithms, which are of the same form and length and which use the same key generation and key distribution services, can co-exist such that the keys used with the stronger algorithm (i.e., DEA) cannot be attacked or weakened by treating them as keys belonging to the weaker algorithm (i.e., CMD) and using the provided CDM-based cryptographic services as an effective means to attack the stronger (DEA-based) keys.
One method for allowing DEA and CDM keys of the same form and length to co-exist within the same cryptographic system is to define separate key types and control vectors, i.e., to cryptographically "tag" each different type of key, and to use a means of control vector encryption to couple the control vector to the key.
U.S. Pat. Nos. 4,941,176, 4,918,728, 4,924,514, 4,924,515, 4,993,069, 5,007,089, and patent application Ser. Nos. 07/596,637, and 07/574,012, cited above, describe cryptographic instructions and key management capabilities based on control vectors. These concepts could be extended to include a new data key type called "CDM data key", which would operate with a new set of CDM-based Encipher and Decipher services. While this is a possible solution, it introduces an added level of complexity into the key management architecture. An alternative method is to make the key weakening process an irreversible process bound together with the CDM algorithm itself, such that knowledge of a weakened key, if revealed, would not reveal information about the strong key from which it was derived.
Cryptographic one-way functions are described in the prior art, but do not teach how such a one-way function can be used beneficially in a key-weakening process. For example, U.S. Pat. No. 4,908,861 to Brachtl discloses a method for calculating a one-way function of an input. The method makes use of a simple kernel function wherein an input is encrypted with a DEA key and then followed by Exclusive-OR operation involving the input and the output ciphertext. The kernel function provides a very simple one-way function that can be used as a building block to provide a much stronger one-way function. Brachtl et al. does not teach protecting an input key used within a key-weakening process.